﻿#define _CRT_SECURE_NO_WARNINGS 1


//https://leetcode.cn/problems/maximum-subarray/
//最⼤⼦数组和
class Solution {
public:
    int maxSubArray(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n + 1);
        int ret = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            int x = nums[i - 1];
            dp[i] = max(x, dp[i - 1] + x);
            ret = max(dp[i], ret);
        }
        return ret;
    }
};

//https://leetcode.cn/problems/maximum-product-subarray/
//乘积最⼤⼦数组
class Solution {
public:
    int maxProduct(vector<int>& nums)
    {
        int  n = nums.size();
        vector<int> f(n + 1);
        auto g = f;
        f[0] = g[0] = 1;
        int ret = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            int x = nums[i - 1];
            if (nums[i - 1] > 0)
            {
                f[i] = max(x, f[i - 1] * x);
                g[i] = min(x, g[i - 1] * x);
            }
            else if (nums[i - 1] < 0)
            {
                f[i] = max(x, g[i - 1] * x);
                g[i] = min(x, f[i - 1] * x);
            }
            ret = max(ret, f[i]);
        }
        return ret;
    }
};



//https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/
//乘积为正数的最⻓⼦数组

class Solution {
public:
    int getMaxLen(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n + 1);
        auto g = f;
        int ret = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            if (nums[i - 1] > 0)
            {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            }
            else if (nums[i - 1] < 0)
            {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = max(ret, f[i]);
        }
        return ret;
    }
};


//https://leetcode.cn/problems/arithmetic-slices/description/
//等差数列划分

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n);
        int sum = 0;
        for (int i = 2; i < n; i++)
        {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])
            {
                dp[i] = dp[i - 1] + 1;
            }
            sum += dp[i];
        }
        return sum;
    }
};


//https://leetcode.cn/problems/longest-turbulent-subarray/
//最⻓湍流⼦数组

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr)
    {

        int n = arr.size();
        vector<int> f(n, 1);
        auto g = f;
        int maxf = 1, maxg = 1;
        for (int i = 1; i < n; i++)
        {
            if (arr[i - 1] - arr[i] < 0) f[i] = g[i - 1] + 1;
            else if (arr[i - 1] - arr[i] > 0)  g[i] = f[i - 1] + 1;
            maxf = max(maxf, f[i]);
            maxg = max(maxg, g[i]);
        }
        return max(maxf, maxg);
    }
};

//https://leetcode.cn/problems/word-break/
//单词拆分

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        int n = s.size();
        unordered_set<string> hash;
        for (auto& s : wordDict) hash.insert(s);
        //创建dp
        vector<bool> dp(n + 1);
        //初始
        dp[0] = true;
        s = ' ' + s;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j >= 1; j--)
            {
                if (dp[j - 1] == true && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

//环绕字符串中唯⼀的⼦字符串
//https://leetcode.cn/problems/unique-substrings-in-wraparound-string/description/
class Solution {
public:
    int findSubstringInWraproundString(string s)
    {
        int n = s.size();
        //创建dp
        vector<int> dp(n, 1);
        for (int i = 1; i < n; i++)
        {
            if (s[i - 1] + 1 == s[i] || s[i - 1] == 'z' && s[i] == 'a')
                dp[i] += dp[i - 1];
        }
        int hash[26] = { 0 };
        for (int i = 0; i < n; i++)
        {
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }
        int sum = 0;
        for (auto n : hash) sum += n;
        return sum;
    }
};

